Corelab Seminar
2013-2014
Prof. Vangelis Paschos (U. Paris-Dauphine)
On the MAXIMUM MINIMAL VERTEX COVER problem
Abstract.
This talk addresses the MAXIMUM MINIMAL VERTEX COVER problem, which is
the maximization version of the well studied INDEPENDENT DOMINATING
SET problem, known to be NP-hard and highly inapproximable in
polynomial time. Tight approximation results for this problem on
general graphs are presented, namely, a polynomial time approximation
algorithm that guarantees an $n^{-1/2}$ approximation ratio, while
showing that unless P is not equal to NP, the problem is
inapproximable within ratio $n^{\varepsilon-(1/2)}$ for any strictly
positive $\varepsilon$. It is also shown that the problem is
fixed-parameter tractable with respect to the size of an optimal
solution and to the size of a maximum matching.